package two.chapter_5.c5_1;

import two.chapter_1.c1_1.Printer;

import java.security.Principal;

/**
 * 低位优先的等长字符串排序
 */
public class LSD {

    /**
     * @param a
     */
    public static void sort(String[] a) {
        int N = a.length;
        int R = 256;//扩展的ASCII表有256个字符
        int w = a[0].length();//
        String aux[] = new String[N];
        for (int i = w - 1; i >= 0; i--) {
            int count[] = new int[R + 1];
            //统计频率
            for (int j = 0; j < N; j++) {
                count[a[j].charAt(i) + 1]++;
            }
            //频率转索引
            for (int r = 0; r < R; r++) {
                count[r + 1] += count[r];
            }
            //分类
            for (int k = 0; k < N; k++) {
                aux[count[a[k].charAt(i)]++] = a[k];
            }

            //回写
            for (int k = 0; k < N; k++) {
                a[k] = aux[k];
            }

        }
    }


    public static void main(String[] args) {
        String[] a = {
                "4PGC938",
                "2IYE230",
                "3CIO720",
                "1ICK750",
                "1OHV845"
        };
        LSD.sort(a);

        Printer.printArray(a);

    }
}
